package weeny.kdtree;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

import edu.wlu.cs.levy.kdTree.KDTree;
import edu.wlu.cs.levy.kdTree.exception.KeyDuplicateException;
import edu.wlu.cs.levy.kdTree.exception.KeySizeException;

/**
 * Utility to maintain a KDTree to store any data, so you can quickly search for
 * the nearest neighbors for a given query. Basically there are two types of
 * functions: add function and nearest function.
 * 
 * Since KDTree does not allow duplicated nodes, so we keep this information by
 * ourself. There is a keepDuplicate flag when do the inserting. If the flag is
 * on and multiple nodes are mapped to the same location in the hyperspace, they
 * are stored in a map (first-one-at-that-location => everyone-at-that-location)
 * To access the list, you can call nearestList functions.
 * 
 * @author weeny
 *
 */
public abstract class AbstractKdTreeUtil {
	private KDTree tree = null;
	/**
	 * Create a new double array based on the passed-in obj. You should override
	 * this function to get your customaized array format representation.
	 */
	protected abstract double[] toArray(Object obj);
	
	private void initTree(Object node){
		tree = new KDTree(toArray(node).length);
	}
	/**
	 * Add everything in coll to this KDTree.
	 * @see #add(Object, boolean)
	 */
	public void addCollection(Collection coll, boolean ignoreDuplicate){
		if (coll == null || coll.isEmpty()) {
			return;
		}
		if (tree == null) {
			initTree(coll.iterator().next());
		}
		for (Object object : coll) {
			add(object, ignoreDuplicate);
		}
	}
	private Map keyMapper = new HashMap();
	/**
	 * Add everything in this collection, ignoring duplicated entries
	 */
	public void addCollection(Collection c){
		addCollection(c, false);
	}
	/**
	 * Add everything in this iterator, igonring duplicated entries
	 */
	public void addIterator(Iterator it){
		addIterator(it, false);
	}
	
	/**
	 * Add this object to this KDTree, keepDuplicate indicates if we need to
	 * remember this entity if it is a duplicate of somthing already being added
	 * before.
	 */
	public void add(Object object, boolean keepDuplicate){
		if (tree == null) {
			initTree(object);
		}
		try {
			tree.insert(toArray(object), object);
		} catch (KeySizeException e) {
			e.printStackTrace();
		} catch (KeyDuplicateException e) {
			if(!keepDuplicate){
				e.printStackTrace();
			}
			else{
				Object n = nearest(object);
				if (keyMapper.containsKey(n)){
					((List)keyMapper.get(n)).add(object);
				}
				else{
					List list = new ArrayList();
					list.add(n);
					list.add(object);
					keyMapper.put(n, list);
				}
			}
		}
	}
	/**
	 * Add this object to this KDTree, ignore it if it has been added before
	 */
	public void add(Object object){
		add(object, false);
	}
	/**
	 * Add everything in this iterator to this KDtree
	 * @see KdTreeUtil#add(Object, boolean)
	 */
	public void addIterator(Iterator it, boolean keepDuplicate){
		if (it == null) {
			return;
		}
		while (it.hasNext()){
			add(it.next(), keepDuplicate);
		}
	}
	/**
	 * Get the nearest entity list from the query
	 * @return an List, which could be null if KDtree does not exist or query
	 * is null or anything goes wrong during query
	 */
	public List nearestList(Object query){
		Object n = nearest(query);
		if (n == null) {
			return null;
		}
		if (keyMapper.containsKey(n)) {
			return (List) keyMapper.get(n);
		}
		else{
			List list = new ArrayList(1);
			list.add(n);
			return list;
		}
	}
	/**
	 * Get the nearest n entity lists from the query
	 * @return an List<List>, which could be null if KDtree does not exist or
	 * query is null or anything goes wrong during query
	 */
	public List<List> nearestList(Object query, int n){
		Object[] ns = nearest(query, n);
		if (ns == null) {
			return null;
		}
		List<List> result = new ArrayList();
		for (Object object : ns) {
			if (keyMapper.containsKey(object)) {
				result.add((List)keyMapper.get(object));
			}
			else{
				List list = new ArrayList(1);
				list.add(object);
				result.add(list);
			}
		}
		return result;
	}
	/**
	 * Get the nearest entity from the query
	 * @return an Object, which could be null if KDtree does not exist or query
	 * is null or anything goes wrong during query
	 */
	public Object nearest(Object query){
		if (tree == null || query == null) {
			return null;
		}
		Object result = null;
		try {
			result = tree.nearest(toArray(query));
		} catch (KeySizeException e) {
			e.printStackTrace();
		}
		return result;
	}
	/**
	 * Get the nearest n entities from the query
	 * @return an Object array, which could be null if KDtree does not exist or
	 * query is null or anything goes wrong during query
	 */
	public Object[] nearest(Object query, int n){
		if (tree == null || query == null) {
			return null;
		}
		Object[] result = null;
		try {
			result = tree.nearest(toArray(query), n);
		} catch (KeySizeException e) {
			e.printStackTrace();
		} catch (IllegalArgumentException e) {
			e.printStackTrace();
		}
		return result;
	}
}